package com.camus.verify.algorithm;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.util.StopWatch;

import com.camus.framework.common.CommonConstant;
import com.camus.verify.algorithm.impl.SubsetAlgorithmOfDistinctRecursion4BigDecimal;
import com.camus.verify.algorithm.impl.SubsetAlgorithmOfSlideWindow4BigDecimal;
import com.camus.verify.algorithm.impl.SubsetAlgorithmOfSortPruningRecursion4BigDecimal;
import com.camus.verify.bo.TargetSumParam;
import com.google.common.collect.Lists;

import cn.hutool.json.JSONUtil;

public class SubsetAlgorithmAssembler4BigDecimal<K> {

	private static final Logger log = LoggerFactory.getLogger(SubsetAlgorithmAssembler4BigDecimal.class);

	public List<K> findSubset(List<K> candidateList, Function<K, BigDecimal> func, BigDecimal target,
			BigDecimal tolerance) {
		if (log.isDebugEnabled()) {
			log.debug("目标和算法,开始:{}", JSONUtil.toJsonStr(TargetSumParam.of(Lists.newArrayList(target),
					candidateList.stream().map(t -> func.apply(t)).collect(Collectors.toList()), target, tolerance)));
		}

		// 入参转化
		BigDecimal upper = target.add(tolerance.abs());
		BigDecimal lower = target.subtract(tolerance.abs());
		MatchTarget[] candidateArr = new MatchTarget[candidateList.size()];
		for (int i = 0; i < candidateArr.length; i++) {
			candidateArr[i] = new MatchTarget(candidateList.get(i), func.apply(candidateList.get(i)));
		}

		// 获取子集
		// 先使用滑动窗口算法
		SubsetAlgorithm4BigDecimal algorithm = new SubsetAlgorithmOfSlideWindow4BigDecimal();
		MatchTarget[] subsetArr = null;
		StopWatch sw = new StopWatch();
		if (log.isDebugEnabled()) {
			log.debug("目标和算法(滑动窗口)，预估复杂度={}", candidateList.size() * (candidateList.size() + 1) / 2);
			SubsetAlgorithm4BigDecimal.counter.remove();
			sw.start("目标和算法(滑动窗口)");
			subsetArr = algorithm.findSubsetWithinRange(candidateArr, lower, upper);
			sw.stop();
			log.debug("目标和算法(滑动窗口)，实际复杂度={}", SubsetAlgorithm4BigDecimal.counter.get().longValue());
		} else {
			subsetArr = algorithm.findSubsetWithinRange(candidateArr, lower, upper);
		}
		if (subsetArr == null || subsetArr.length == 0) {
			// 使用递归算法
			Map<BigDecimal, List<Integer>> indexListMap = new HashMap<>();
			for (int i = 0; i < candidateArr.length; i++) {
				List<Integer> indexList = indexListMap.get(candidateArr[i].getTarget());
				if (indexList == null) {
					indexList = new ArrayList<>();
					indexListMap.put(candidateArr[i].getTarget(), indexList);
				}
				indexList.add(i);
			}
			long complexity = 1;
			for (List<Integer> indexList : indexListMap.values()) {
				complexity = complexity * (indexList.size() + 1);
			}
			String algorithmName = "";
			if (candidateList.size() - indexListMap.keySet().size() >= 3 && complexity < (long)Math.pow(2, 27)) {
				algorithmName = "目标和算法(消重递归)";
				algorithm = new SubsetAlgorithmOfDistinctRecursion4BigDecimal();
			} else {
				algorithmName = "目标和算法(排序剪枝递归)";
				complexity = (long)Math.pow(2, candidateList.size());
				algorithm = new SubsetAlgorithmOfSortPruningRecursion4BigDecimal();
			}
			if (log.isDebugEnabled()) {
				log.debug(algorithmName+"，预估复杂度={}", complexity);
				SubsetAlgorithm4BigDecimal.counter.remove();
				sw.start(algorithmName);
				subsetArr = algorithm.findSubsetWithinRange(candidateArr, lower, upper);
				sw.stop();
				log.debug(algorithmName+"，实际复杂度={}", SubsetAlgorithm4BigDecimal.counter.get().longValue());
				log.debug(sw.prettyPrint());
			} else {
				subsetArr = algorithm.findSubsetWithinRange(candidateArr, lower, upper);
			}
		}
		if (subsetArr == null) {
			subsetArr = new MatchTarget[] {};
		}
		if (log.isDebugEnabled()) {
			if (subsetArr.length > 0) {
				log.debug("目标和算法,结果:" + CommonConstant.LOGGER_FORMATER_PARAM_RETURN,
						JSONUtil.toJsonStr(TargetSumParam.of(Lists.newArrayList(target),
								candidateList.stream().map(t -> func.apply(t)).collect(Collectors.toList()), target,
								tolerance)),
						JSONUtil.toJsonStr(
								Arrays.stream(subsetArr).map(t -> (K) t.getRef()).collect(Collectors.toList())));
			} else {
				log.debug("目标和算法,无结果:" + CommonConstant.LOGGER_FORMATER_PARAM_RETURN,
						JSONUtil.toJsonStr(TargetSumParam.of(Lists.newArrayList(target),
								candidateList.stream().map(t -> func.apply(t)).collect(Collectors.toList()), target,
								tolerance)),
						null);
			}
		}

		// 结果转化
		if (subsetArr.length == 0) {
			return new ArrayList<>();
		}
		return Arrays.stream(subsetArr).map(t -> (K) t.getRef()).collect(Collectors.toList());
	}

}
